/* memory.c
 * By: Teresa Hume
 * Date Created: March 19, 2011
 * Date Modified: April 1st, 2011
 * Modified by: Erin Szilagyi
 *              Samuel Ferguson
 */

#include <memory.h>
#include <definitions.h>
#include <xxxio.h>

/* points to the head of the list containing free memory */
union block_header *free_list;

/* function to allocate memory within a process's memory space */
void* malloc(unsigned size)
{
  return 0;
}

/* function to free memory within a process's memory space */
void free(void* pointer)
{
  return;
}

/* function to allocate a process memory space from the free list */
struct mm_struct* allocate_process()
{
  /* roxy is pointer to the previous union block_header in loop*/
  /* Memory looks like: roxy->next = boxy */
  union block_header *boxy,*roxy = NULL;
  union block_header *process_block, *free_block = NULL;
  if(free_list == NULL){
    xprintf("memory.c line:%i failed to init the process block\n",__LINE__);
  }
  /* find block that fits (fits = process_size <= union block_size) */
  /* Process standard size: 1MB */
  for(boxy = free_list; boxy != NULL; boxy = boxy->s.next){
    if(boxy->s.size >= process_size){
      /* found */
      /* seperate block into process_block and free_block */
      process_block = boxy;
      if(boxy->s.size > process_size){
	/* xprintf("memory.c line:%i boxy = %i\n", */
	/* 	__LINE__, boxy); */
	/* xprintf("memory.c line:%i boxy + boxy = %i\n", */
	/* 	__LINE__, (unsigned)boxy + (unsigned)boxy); */
	/* xprintf("memory.c line:%i process_size = %i\n", */
	/* 	__LINE__, process_size); */
	/* xprintf("memory.c line:%i process_size + process_size = %i\n", */
	/* 	__LINE__, process_size + process_size); */
	free_block = (unsigned)boxy + process_size;
	/* xprintf("memory.c line:%i free_block = %i\n", */
	/* 	__LINE__, free_block); */
	free_block->s.size = boxy->s.size - process_size;
	/* xprintf("memory.c line:%i free_block->s.size = %i\n", */
	/* 	__LINE__,free_block->s.size); */
	free_block->s.next = boxy->s.next;
	process_block->s.next = free_block;
      }

      process_block->s.size = process_size;

      /* add free_block to free_list && removing process_block from list */
      if(roxy==NULL){/* could also say if(boxy == free_list) */
	/* xprintf("memory.c line:%i free_list = free_block\n",__LINE__); */
	free_list = free_block;	/* free_block is the new head of list*/
      }
      else if(free_block != NULL)  /* else if free_block was made */
	roxy->s.next = free_block; /* add it to the list */
      
      /* intialize an mm_struct and return mm_struct*/
      return mm_init((struct mm_struct *)
		     (process_block+sizeof(union block_header)), (void*)process_block);
      
    }
    roxy=boxy;
  }
  xprintf("memory.c line:%i failed to init the process block\n",__LINE__);
  return NULL;
}

/* function to add now un-used memory to the free list and defragment blocks */
void free_process(union block_header *boxy)
{
  union block_header *roxy; /* is the pointer current free_list entry */
  /* loop through free_list and see where it fits */
  for(roxy=free_list; roxy->s.next != NULL; roxy=roxy->s.next){
    if(roxy < boxy && (roxy->s.next == NULL || roxy->s.next > boxy)){
      boxy->s.next = roxy->s.next;
      roxy->s.next = boxy;		    
      free_merge(roxy);
      return;
    }
  }
  return;
}

/* function to merge free memory blocks when a process's memory is 
   no longer in use */
void free_merge(union block_header *boxy)
{
  if(boxy+boxy->s.size == boxy->s.next){
    boxy->s.size += boxy->s.next->s.size;
    boxy->s.next = boxy->s.next->s.next;
    free_merge(boxy); /* XXX - A recursive call to merge sequential blocks */
  }
  return;
}

/* function to initialize an mm_struct */
struct mm_struct* mm_init(struct mm_struct* process, void* boxy)
{
  process->start_brk = 
    sizeof(union block_header) + sizeof(struct mm_struct) + boxy;
  process->brk = boxy + (process_size >> 1);
  process->mmap_base = boxy;
  process->start_stack = boxy + process_size;
  /*end_data, start_data, end_code, and start_code not handled yet
    MineCraft: "You can do that with LEGOs"*/
  return process;
}

/* function to set up the free_list at startup */
void init_mem(void)
{
  unsigned int i;
  struct e820_t foxy;  /* foxy is an entry in the e820 */
  struct e820_t* e820;  /* the e820 is an array */
  free_list = NULL;

  /* loop through the e820 struct */
  e820 = (struct e820_t*)&e820_raw;
  for(i=0; i < e820_counter; i++){	
    foxy = e820[i];

    /* if e820 entry is usable */
    if(foxy.type == 1){
      /* xprintf("memory.c line:%i foxy.base_address_low = %i\n",__LINE__, foxy.base_address_low); */
      /* xprintf("memory.c line:%i foxy.length_low = %i\n",__LINE__, foxy.length_low); */

      /* This code reserves the first KERNEL_SIZE bytes in memory for xxxos */
      if(foxy.base_address_low < KERNEL_SIZE){
    	if(foxy.base_address_low + foxy.length_low < KERNEL_SIZE){
	  /* xprintf("memory.c line:%i continuing\n",__LINE__); */
    	  continue; /* ignore entries in the first KERNEL_SIZE bytes */
	}
    	else{ /* resize entries which are partially in KERNEL_SIZE bytes */
    	  foxy.length_low -= KERNEL_SIZE - foxy.base_address_low;
    	  foxy.base_address_low = KERNEL_SIZE;
    	}
      }
      /* make a block and add to list */
      free_list_add(make_block(foxy));
    }
  }
  return; 
}

/* function to make a memory block from an e820_t entry */
union block_header *make_block (struct e820_t entry)
{
  /* 32-bit system, therefore only use base_address_low for return value*/
  union block_header *rv = (union block_header*) entry.base_address_low;
  rv->s.size = entry.length_low;
  rv->s.next = NULL;
  return rv;
}

/* function to add a memory block to the free list on startup */
void free_list_add(union block_header *boxy)
{
  /* Assumption: e820 map is sequential */
  union block_header *roxy; /*tail of free_list */
  if(free_list == NULL){
    free_list = boxy;
    /* xprintf("memory.c line:%i free_list head set\n",__LINE__); */
  } 
  else {
    for(roxy=free_list; roxy->s.next != NULL; roxy=roxy->s.next); /* O(n^2) */
    roxy->s.next = boxy;
  }
  return;
}

